#pragma once

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include"graph.h"

using namespace std;

const int NUMBER_OF_GRAPH_TYPES = 9;
const int NUMBER_OF_CYCLE_GRAPH_TYPES = 4;

vector<int> get_shuffled_vertices(int vertices_number)
{
	vector<int> shuffled_vertices;
	for (int vertex = 0; vertex < vertices_number; ++vertex)
		shuffled_vertices.push_back(vertex);
	random_shuffle(shuffled_vertices.begin(), shuffled_vertices.end());
	return shuffled_vertices;
}

vector<pair <int, int> > get_distinct_edges_for_random_graph(int vertices_number, int max_edges_number)
{
	set<pair<int, int> > edges_set;
	for (int i = 0; i < max_edges_number; ++i)
	{
		pair <int, int> edge(rand() % vertices_number, rand() % vertices_number);
		edges_set.insert(edge);
	}
	vector<pair<int, int> > edges_list(edges_set.begin(), edges_set.end());
	return edges_list;
}

vector<pair <int, int> > get_distinct_edges_for_random_acycle_graph(int vertices_number, int max_edges_number)
{
	vector<int> shuffled_vertices = get_shuffled_vertices(vertices_number);
	set<pair<int, int> > edges_set;
	for (int i = 0; i < max_edges_number; ++i)
	{
		pair <int, int> edge(rand() % vertices_number, rand() % vertices_number);
		if (edge.first > edge.second)
			swap(edge.first, edge.second);
		edge.first = shuffled_vertices[edge.first];
		edge.second = shuffled_vertices[edge.second];
		edges_set.insert(edge);
	}
	vector<pair<int, int> > edges_list(edges_set.begin(), edges_set.end());
	return edges_list;
}

vector<pair <int, int> > get_edges_for_full_graph(int vertices_number)
{
	vector<pair<int, int> > edges;
	for (int vertex1 = 0; vertex1 < vertices_number; ++vertex1)
		for (int vertex2 = 0; vertex2 < vertices_number; ++vertex2)
			if (vertex1 != vertex2)
			{
				pair<int, int> edge(vertex1, vertex2);
				edges.push_back(edge);
			}
	return edges;
}

vector<pair <int, int> > get_edges_for_halffull_graph(int vertices_number)
{
	vector<int> shuffled_vertices = get_shuffled_vertices(vertices_number);
	vector<pair<int, int> > edges;
	for (int i = 0; i < vertices_number - 1; ++i)
		for (int j = i + 1; j < vertices_number; ++j)
		{
			pair<int, int> edge(shuffled_vertices[i], shuffled_vertices[j]);
			edges.push_back(edge);
		}
	return edges;
}

vector<pair <int, int> > get_edges_for_cycle_graph(int vertices_number)
{
	vector<int> shuffled_vertices = get_shuffled_vertices(vertices_number);
	vector<pair<int, int> > edges;
	for (int i = 0; i < vertices_number; ++i)
	{
		pair<int, int> edge(shuffled_vertices[i], shuffled_vertices[(i + 1) % vertices_number]);
		edges.push_back(edge);
	}
	return edges;
}

vector<pair <int, int> > get_edges_for_chain_graph(int vertices_number)
{
	vector<int> shuffled_vertices = get_shuffled_vertices(vertices_number);
	vector<pair<int, int> > edges;
	for (int i = 0; i < vertices_number - 1; ++i)
	{
		pair<int, int> edge(shuffled_vertices[i], shuffled_vertices[i + 1]);
		edges.push_back(edge);
	}
	return edges;
}

vector<pair <int, int> > get_edges_for_tree_graph(int vertices_number)
{
	vector<int> shuffled_vertices = get_shuffled_vertices(vertices_number);
	vector<pair<int, int> > edges;
	for (int i = 1; i < vertices_number; ++i)
	{
		pair<int, int> edge(shuffled_vertices[rand() % i], shuffled_vertices[i]);
		edges.push_back(edge);
	}
	return edges;
}

vector<pair <int, int> > get_edges_for_functional_graph(int vertices_number)
{
	vector<pair<int, int> > edges;
	for (int vertex = 0; vertex < vertices_number; ++vertex)
	{
		pair<int, int> edge(vertex, rand() % vertices_number);
		edges.push_back(edge);
	}
	return edges;
}

vector<pair <int, int> > get_edges_for_empty_graph(int vertices_number)
{
	vector<pair<int, int> > edges;
	return edges;
}

vector<pair <int, int> > get_edges_for_my_acycle_graph(int vertices_number)
{
	vector<int> shuffled_vertices = get_shuffled_vertices(vertices_number);
	vector<pair<int, int> > edges;
	for (int i = 0; i < vertices_number - 3; ++i)
	{
		pair<int, int> edge1(shuffled_vertices[i], shuffled_vertices[i + 1]);
		pair<int, int> edge2(shuffled_vertices[i], shuffled_vertices[i + 2]);
		edges.push_back(edge1);
		edges.push_back(edge2);
	}
	pair<int, int> edge(shuffled_vertices[vertices_number - 1], shuffled_vertices[vertices_number - 1]);
	edges.push_back(edge);
	return edges;
}

vector<pair <int, int> > get_edges_for_my_cycle_graph(int vertices_number)
{
	vector<int> shuffled_vertices = get_shuffled_vertices(vertices_number);
	vector<pair<int, int> > edges;
	for (int i = 0; i < vertices_number - 3; ++i)
	{
		pair<int, int> edge1(shuffled_vertices[i], shuffled_vertices[i + 1]);
		pair<int, int> edge2(shuffled_vertices[i], shuffled_vertices[i + 2]);
		edges.push_back(edge1);
		edges.push_back(edge2);
	}
	pair<int, int> edge1(shuffled_vertices[vertices_number - 2], shuffled_vertices[0]);
	pair<int, int> edge2(shuffled_vertices[vertices_number - 1], shuffled_vertices[vertices_number - 1]);
	edges.push_back(edge1);
	edges.push_back(edge2);
	return edges;
}

string graph_name(int graph_type)
{
	assert(graph_type < NUMBER_OF_GRAPH_TYPES);
	if (graph_type == 0)
		return("FULL");
	if (graph_type == 1)
		return("CYCLE");
	if (graph_type == 2)
		return("FUNCTIONAL");
	if (graph_type == 3)
		return("MY CYCLE");
	if (graph_type == 4)
		return("HALF-FULL");
	if (graph_type == 5)
		return("CHAIN");
	if (graph_type == 6)
		return("TREE");
	if (graph_type == 7)
		return("MY ACYCLE");
	if (graph_type == 8)
		return("EMPTY");
	return "RANDOM";
}

vector<pair<int, int> > get_edges_for_graph_by_type(int vertices_number, int graph_type)
{
	string graphname = graph_name(graph_type);
	if (graphname == "FULL")
		return get_edges_for_full_graph(vertices_number);
	if (graphname == "CYCLE")
		return get_edges_for_cycle_graph(vertices_number);
	if (graphname == "FUNCTIONAL")
		return get_edges_for_functional_graph(vertices_number);
	if (graphname == "MY CYCLE")
		return get_edges_for_my_cycle_graph(vertices_number);
	if (graphname == "HALF-FULL")
		return get_edges_for_halffull_graph(vertices_number);
	if (graphname == "CHAIN")
		return get_edges_for_chain_graph(vertices_number);
	if (graphname == "TREE")
		return get_edges_for_tree_graph(vertices_number);
	if (graphname == "MY ACYCLE")
		return get_edges_for_my_acycle_graph(vertices_number);
	if (graphname == "EMPTY")
		return get_edges_for_empty_graph(vertices_number);
}